|
In graph theory, Turán's theorem is a result on the number of edges in a ''K''''r''+1-free graph. An -vertex graph that does not contain any -vertex clique may be formed by partitioning the set of vertices into parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. We call the resulting graph the Turán graph . Turán's theorem states that the Turán graph has the largest number of edges among all -free -vertex graphs. Turán graphs were first described and studied by Hungarian mathematician Pál Turán in 1941, though a special case of the theorem was stated earlier by Mantel in 1907. ==Formal statement== :Turán's Theorem. Let be any graph with vertices, such that is ''K''''r''+1 -free. Then the number of edges in is at most :: An equivalent formulation is the following: :Turán's Theorem (Second Formulation). Among the -vertex simple graphs with no -cliques, has the maximum number of edges. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turán's theorem」の詳細全文を読む スポンサード リンク
|